<!-- HTML header for doxygen 1.8.13-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.14"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Taskflow Handbook</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link rel="icon" type="image/x-icon" href="favicon.ico" />
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
  $(document).ready(initResizable);
/* @license-end */</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname"><a href="https://taskflow.github.io/">Taskflow</a>
   &#160;<span id="projectnumber">3.0.0-Master-Branch</span>
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.14 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
var searchBox = new SearchBox("searchBox", "search",false,'Search');
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
/* @license-end */</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(document).ready(function(){initNavTree('graphtraversal.html','');});
/* @license-end */
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">Graph Traversal </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>We study the graph traversal problem by visiting each vertex in parallel following their edge dependencies. Traversing a graph is a fundamental building block of many graph applications especially for large-scale graph analytics.</p>
<h1><a class="anchor" id="GraphTraversalProblemFormulation"></a>
Problem Formulation</h1>
<p>Given a directed acyclic graph (DAG), i.e., a graph that has no cycles, we would like to traverse each vertex in order without breaking dependency constraints defined by edges. The following figure shows a graph of six vertices and seven edges. Each vertex represents a particular task and each edge represents a task dependency between two tasks.</p>
<div class="image">
<object type="image/svg+xml" data="task-level-parallelism.svg" width="50%">task-level-parallelism.svg</object>
</div>
<p>Traversing the above graph in parallel, the maximum parallelism we can acquire is three. When Task1 finishes, we can run Task2, Task3, and Task4 in parallel.</p>
<h1><a class="anchor" id="GraphTraversalGraphRepresentation"></a>
Graph Representation</h1>
<p>We define the data structure of our graph. The graph is represented by an array of nodes of the following structure:</p>
<div class="fragment"><div class="line"><span class="keyword">struct </span>Node {</div><div class="line">  <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/string/basic_string.html">std::string</a> name;</div><div class="line">  <span class="keywordtype">size_t</span> idx;                          <span class="comment">// index of the node in a array</span></div><div class="line">  <span class="keywordtype">bool</span> visited {<span class="keyword">false</span>};</div><div class="line"></div><div class="line">  <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/atomic/atomic.html">std::atomic&lt;size_t&gt;</a> dependents {0};  <span class="comment">// number of incoming edges</span></div><div class="line">  <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/container/vector.html">std::vector&lt;Node*&gt;</a> successors;       <span class="comment">// number of outgoing edges</span></div><div class="line"></div><div class="line">  <span class="keywordtype">void</span> precede(Node&amp; n) {</div><div class="line">    successors.emplace_back(&amp;n);</div><div class="line">    n.dependents ++;</div><div class="line">  }</div><div class="line">};</div></div><!-- fragment --><p>Based on the data structure, we randomly generate a DAG using ordered edges.</p>
<div class="fragment"><div class="line"><a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/memory/unique_ptr.html">std::unique_ptr&lt;Node[]&gt;</a> make_dag(<span class="keywordtype">size_t</span> num_nodes, <span class="keywordtype">size_t</span> max_degree) {</div><div class="line">  </div><div class="line">  <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/memory/unique_ptr.html">std::unique_ptr&lt;Node[]&gt;</a> nodes(<span class="keyword">new</span> Node[num_nodes]);</div><div class="line">  </div><div class="line">  <span class="comment">// Make sure nodes are in clean state</span></div><div class="line">  <span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> i=0; i&lt;num_nodes; i++) {</div><div class="line">    nodes[i].idx = i;</div><div class="line">    nodes[i].name = <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/string/basic_string/to_string.html">std::to_string</a>(i);</div><div class="line">  }</div><div class="line"></div><div class="line">  <span class="comment">// Create a DAG by randomly insert ordered edges</span></div><div class="line">  <span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> i=0; i&lt;num_nodes; i++) {</div><div class="line">    <span class="keywordtype">size_t</span> degree {0};</div><div class="line">    <span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> j=i+1; j&lt;num_nodes &amp;&amp; degree &lt; max_degree; j++) {</div><div class="line">      <span class="keywordflow">if</span>(std::rand() % 2 == 1) {</div><div class="line">        nodes[i].precede(nodes[j]);</div><div class="line">        degree ++;</div><div class="line">      }</div><div class="line">    }</div><div class="line">  }</div><div class="line"></div><div class="line">  <span class="keywordflow">return</span> nodes;</div><div class="line">}</div></div><!-- fragment --><p>The function, <code>make_dag</code>, accepts two arguments, <code>num_nodes</code> and <code>max_degree</code>, to restrict the number of nodes in the graph and the maximum number of outgoing edges of every node.</p>
<h1><a class="anchor" id="GraphTraversalStaticTraversal"></a>
Static Traversal</h1>
<p>We create a taskflow to traverse the graph using static tasks (see <a class="el" href="chapter1.html">C1: Static Tasking</a>). Each task does nothing but marks <code>visited</code> to <code>true</code> and subtracts <code>dependents</code> from one, both of which are used for validation after the graph is traversed. In practice, this computation may be replaced with a heavy function.</p>
<div class="fragment"><div class="line"><a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line"><a class="code" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div><div class="line"></div><div class="line"><a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/memory/unique_ptr.html">std::unique_ptr&lt;Node[]&gt;</a> nodes = make_dag(100000, 4);</div><div class="line"><a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/container/vector.html">std::vector&lt;tf::Task&gt;</a> tasks;</div><div class="line"></div><div class="line"><span class="comment">// create the traversal task for each node</span></div><div class="line"><span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> i=0; i&lt;num_nodes; ++i) {</div><div class="line">  <a class="code" href="classtf_1_1Task.html">tf::Task</a> task = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>([v=&amp;(nodes[i])](){</div><div class="line">    v-&gt;visited = <span class="keyword">true</span>;</div><div class="line">    <span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> j=0; j&lt;v-&gt;successors.size(); ++j) {</div><div class="line">      v-&gt;successors[j]-&gt;dependents.fetch_sub(1);</div><div class="line">    }</div><div class="line">  }).name(nodes[i].name);</div><div class="line"></div><div class="line">  tasks.push_back(task);</div><div class="line">}</div><div class="line"></div><div class="line"><span class="comment">// create the dependency between nodes on top of the graph structure</span></div><div class="line"><span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> i=0; i&lt;num_nodes; ++i) {</div><div class="line">  <span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> j=0; j&lt;nodes[i].successors.size(); ++j) {</div><div class="line">    tasks[i].precede(tasks[nodes[i].successors[j]-&gt;idx]);</div><div class="line">  }</div><div class="line">}</div><div class="line"></div><div class="line">executor.<a class="code" href="classtf_1_1Executor.html#a81f35d5b0a20ac0646447eb80d97c0aa">run</a>(taskflow).wait();</div><div class="line"></div><div class="line"><span class="comment">// after the graph is traversed, all nodes must be visited with no dependents</span></div><div class="line"><span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> i=0; i&lt;num_nodes; i++) {</div><div class="line">  assert(nodes[i].visited);</div><div class="line">  assert(nodes[i].dependents == 0);</div><div class="line">}</div></div><!-- fragment --><p>The code above has two parts to construct the parallel graph traversal. First, it iterates each node and constructs a traversal task for that node. Second, it iterates each outgoing edge of a node and creates a dependency between the node and the other end (successor) of that edge. The resulting taskflow structure is topologically equivalent to the given graph.</p>
<div class="image">
<object type="image/svg+xml" data="graph_traversal_2.svg" width="100%">graph_traversal_2.svg</object>
</div>
<p>With task parallelism, we flow computation naturally with the graph structure. The runtime autonomously distributes tasks across processor cores to obtain maximum task parallelism. You do not need to worry about details of scheduling.</p>
<h1><a class="anchor" id="GraphTraversalDynamicTraversal"></a>
Dynamic Traversal</h1>
<p>We can traverse the graph dynamically using <a class="el" href="classtf_1_1Subflow.html" title="class to construct a subflow graph from the execution of a dynamic task ">tf::Subflow</a> (see <a class="el" href="chapter3.html">C3: Dynamic Tasking</a>). We start from the source nodes of zero incoming edges and recursively spawn subflows whenever the dependency of a node is meet. Since we are creating tasks from the execution context of another task, we need to store the task callable in advance.</p>
<div class="fragment"><div class="line"><a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line"><a class="code" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div><div class="line"></div><div class="line"><span class="comment">// task callable of traversing a node using subflow</span></div><div class="line"><a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/utility/functional/function.html">std::function&lt;void(Node*, tf::Subflow&amp;)&gt;</a> traverse;</div><div class="line"></div><div class="line">traverse = [&amp;] (Node* n, <a class="code" href="classtf_1_1Subflow.html">tf::Subflow</a>&amp; subflow) {</div><div class="line">  assert(!n-&gt;visited);</div><div class="line">  n-&gt;visited = <span class="keyword">true</span>;</div><div class="line">  <span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> i=0; i&lt;n-&gt;successors.size(); i++) {</div><div class="line">    <span class="keywordflow">if</span>(n-&gt;successors[i]-&gt;dependents.fetch_sub(1) == 1) {</div><div class="line">      subflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>([s=n-&gt;successors[i], &amp;traverse](<a class="code" href="classtf_1_1Subflow.html">tf::Subflow</a> &amp;subflow){ </div><div class="line">        traverse(s, subflow); </div><div class="line">      }).<a class="code" href="classtf_1_1Task.html#a08ada0425b490997b6ff7f310107e5e3">name</a>(n-&gt;name);</div><div class="line">    }</div><div class="line">  }</div><div class="line">};</div><div class="line"></div><div class="line"><span class="comment">// create a graph</span></div><div class="line"><a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/memory/unique_ptr.html">std::unique_ptr&lt;Node[]&gt;</a> nodes = make_dag(100000, 4);</div><div class="line"></div><div class="line"><span class="comment">// find the source nodes (no incoming edges)</span></div><div class="line"><a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/container/vector.html">std::vector&lt;Node*&gt;</a> src;</div><div class="line"><span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> i=0; i&lt;num_nodes; i++) {</div><div class="line">  <span class="keywordflow">if</span>(nodes[i].dependents == 0) { </div><div class="line">    src.emplace_back(&amp;(nodes[i]));</div><div class="line">  }</div><div class="line">}</div><div class="line"></div><div class="line"><span class="comment">// create only tasks for source nodes</span></div><div class="line"><span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> i=0; i&lt;src.size(); i++) {</div><div class="line">  taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>([s=src[i], &amp;traverse](<a class="code" href="classtf_1_1Subflow.html">tf::Subflow</a>&amp; subflow){ </div><div class="line">    traverse(s, subflow); </div><div class="line">  }).name(nodes[i].name);</div><div class="line">}</div><div class="line"></div><div class="line">executor.<a class="code" href="classtf_1_1Executor.html#a81f35d5b0a20ac0646447eb80d97c0aa">run</a>(taskflow).wait();</div><div class="line"></div><div class="line"><span class="comment">// after the graph is traversed, all nodes must be visited with no dependents</span></div><div class="line"><span class="keywordflow">for</span>(<span class="keywordtype">size_t</span> i=0; i&lt;num_nodes; i++) {</div><div class="line">  assert(nodes[i].visited);</div><div class="line">  assert(nodes[i].dependents == 0);</div><div class="line">}</div></div><!-- fragment --><div class="image">
<object type="image/svg+xml" data="graph_traversal_1.svg" width="90%">graph_traversal_1.svg</object>
</div>
<p>In general, the dynamic version of graph traversal is slower than the static version due to the overhead incurred by spawning subflows. However, it may be useful for the situation where the graph structure is unknown at once but being partially explored during the traversal. </p>
</div></div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="navelem"><a class="el" href="Examples.html">Learning from Examples</a></li>
    <li class="footer">Generated by
    <a href="http://www.doxygen.org/index.html">
    <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.14 </li>
  </ul>
</div>
</body>
</html>
